package com.zyk.problem;

/**
 * 给你一个数组, 升序的, 和一个线段k
 * 请问这个线段最多能压住多少个数
 *
 * @author zhangsan
 * @date 2021/5/2 19:30
 */
public class CordCoverMaxPoint {

    // 窗口解, 有序不回退. 左右指针, 阔步动计算  O(N)
    public static int maxPoint1(int[] arr, int k) {
        int l = 0, r = 0, n = arr.length;
        int ans = 0;
        while (r < n) {
            while (r < n && arr[r] - arr[l] <= k) {
                r++;
            }
            ans = Math.max(ans, r - l++);
        }
        return ans;
    }

    // 二分, 枚举所有以i结尾往前二分看能阔多少    O(n*logN)
    public static int maxPoint2(int[] arr, int k) {
        int ans = 1, n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = binarySearch(arr, 0, i, arr[i] - k);
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }

    // 在L~R中找到大于等于 target的最左位置
    private static int binarySearch(int[] arr, int l, int r, int target) {
        int m, mostRight = -1;
        while (l <= r) {
            m = (l + r) >> 1;
            if (arr[m] < target) {
                l = m + 1;
            } else { // arr[m] >= target
                mostRight = m;
                r = m - 1;
            }
        }
        return mostRight;
    }


    // for test
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 7, 8, 9, 10, 13, 15};
        int k = 6;
        System.out.println(maxPoint1(arr, k));
        System.out.println(maxPoint2(arr, k));
    }

}
